%\section{Omitted Proofs}
%\label{sec:proofs}
We now give the proofs of Theorems~\ref{thm:optlb} and \ref{thm:adversarial}
from section~\ref{sec:functions}.

\begin{proof}[of Theorem~\ref{thm:optlb}]
Let the target coverage $T_i$ be the budget $B$ for every feature. Then, the
goal of the algorithm is to select a subset of items such that the minimum 
coverage among all features is maximized. Also, $\rho_{\opt} = c_{\opt} B$.

We will prove the following reduction: any algorithm which yields a finite approximation ratio for 
offline instances of this problem with $\rho_{\opt} = \lambda$ 
implies resolution of the following decision problem:
\begin{framed}
\parbox{0.95\columnwidth}{\em Consider an instance of the set cover problem $(X, {\bf S})$ where 
$\bf S$ is a collection of subsets defined on the universe of elements 
$X$.\footnote{\rm Recall that in the set cover problem, the input consists of 
a collection of subsets defined on a universe of elements, and the goal is to decide
whether there exists a sub-collection within a stipulated budget
that covers every element in the universe.}
Suppose the optimal solution contains $\opt$ sets. 
Given a budget $B$, output \yes if $B\geq \lambda\cdot\opt$, \no if $B < \opt$,
and either \yes or \no otherwise.}
\end{framed}
The theorem now follows from standard inapproximability results~\cite{Feige98}.

We now describe the construction of the \diverse problem instance in the reduction.
Each element is mapped to a distinct feature and we create $\lambda$ identical items 
corresponding to each subset. The decision algorithm runs the 
$\lambda$-approximation algorithm on this instance of the diversifier problem with budget $B$ and outputs
\yes if the value of the objective in the solution is at least 1, and \no 
if it is 0. First, consider the case when $B < \opt$. In this case, the 
optimal objective value of the diversifier algorithm is 0, and hence the 
output is \no. Now, suppose $B \geq \lambda\cdot\opt$. In this case, the optimal
objective value of the diversifier algorithm is at least $\lambda$ (by 
choosing $\lambda$ copies of an optimum set cover solution), which implies
that the output is \yes.
\end{proof}

\begin{proof}[of Theorem~\ref{thm:adversarial}]
$T_i$ for every feature $i$ be equal to the budget $B$ and let $B = 2n-1$. 
In the
Consider the following input distribution comprising two rounds. 
Let the target
first round, the input consists of a sequence of $n^2$ items, each containing a 
single feature such that the number of items containing any particular 
feature is $n$. These items are presented in an arbitrary fixed order. 
In the second round, the input consists of $n-1$ items, each containing
the same set of $n-1$ features, where each feature is left out of all these
$n-1$ items with probability $1/n$. Since the coverage on the feature that
is left out in second round is exactly the same as that at the end of the first round, 
the expected objective value attained by any deterministic algorithm for 
this input distribution is at most $(2n-1)/n < 2$. On the other hand, 
the optimal solution always attains a value of $n$ by selecting $n$ items 
from the first round that contain only the feature left out in the second
round, and then all the $n-1$ items from the second round. The theorem 
now follows from Yao's minmax principle~\cite{MotwaniR97}.
\end{proof}
\noindent
